//
// Created by PC on 2023/10/12.
// 埃氏筛法
/*
 * 讲解 https://zhuanlan.zhihu.com/p/146418699
 * https://oj.hterobot.com/?#/question/107719?order=ID&offset=0&limit=20&teamid&name=%E7%B4%A0%E6%95%B0&range=public
 * 21个测试用例:11个通过10个超时
 *
 * https://www.luogu.com.cn/problem/P3912
 * 10个测试用例:9个通过1个超时
 *
 * 107719.区间素数个数
难度 普及+/提高
内存 512MB 时间 3000ms
题目描述
求1~N 之间素数个数。
输入格式
一行一个数
输出格式
一行一个数，表示答案。
输入输出测试点
输入 #1
10
输出 #1
4
说明
对于 40% 的数据，1≤N≤10^6

对于 80% 的数据，1≤N≤10^7

对于 100% 的数据，1≤N≤10^8

 * */
//


#include <iostream>
#include <cmath>

using namespace std;

bool is_prime(long long x)
{
    if (x<2)
        return false;
    else
    {
        for (long long i = 2; i <= int(sqrt(x)); ++i)
        {
            if(x%i==0)
                return false;
        }
        return true;
    }
}
int main()
{
    long long n=100,count=0; //out: 25
    n = 1740948; // out: 130971
//    n= 2115790; //out:156902
//    n = 65090061389;//out: 2728793966
//    cin>>n;
    // 建立一个n+1长度的char数组,每个索引对应一个数,默认都是0,是素数存'y',不是存'n'
    char l[n+1]={0};
//    cout<<is_prime(n);
    for (long long i = 2; i <= n; ++i)
    {
        // 数组中对应的值为0 并且 i是素数
        if (l[i]==0 && is_prime(i) )
        {
            l[i]='y';
            count++;
            for (int j = i; j <=n ; j+=i)
            {
                if(l[j]==0)
                {
                    l[j]='n';
                }
            }
            // i的倍数都不是素数
        }
    }
    cout<<count;
    return 0;
}